package com.gaogzhen.datastructure.tree;

import java.util.Iterator;

/**
 * 二叉搜索树测试
 * @author Administrator
 * @version 1.0
 * @description
 * @date 2022-11-28 20:42
 */
public class TestBst {
    public static void main(String[] args) {
//        System.out.println("R".compareTo("S"));
//        testBst();
//        testRBTDelete();
//         testRBTOrder();
//         testSelect();
        testKeys();
    }

    public static void testKeys() {
        RedBlackTree<String, Integer> rb = new RedBlackTree<>();
//        RedBlackBST<String, Integer> rb = new RedBlackBST<>();
        rb.put("S", 1);
        rb.put("E", 2);
        rb.put("CC", 3);
        rb.put("R", 4);
        rb.put("C", 5);
        rb.put("H", 6);
        rb.put("X", 7);
        rb.put("M", 8);
        rb.put("P", 9);
        rb.put("L", 10);
        System.out.println(rb);
        for (String key : rb.keys("N", "T")) {
            System.out.println(key + "  "  + rb.get(key));
        }
    }

    public static void testSelect() {
        RedBlackTree<String, Integer> rb = new RedBlackTree<>();
//        RedBlackBST<String, Integer> rb = new RedBlackBST<>();
        rb.put("S", 1);
        rb.put("E", 2);
        rb.put("A", 3);
       rb.put("R", 4);
        rb.put("C", 5);
       rb.put("H", 6);
       rb.put("X", 7);
        rb.put("M", 8);
       rb.put("P", 9);
       rb.put("L", 10);

        System.out.println(rb.select(1));
        for(int i = 0; i < rb.size(); i++) {
            System.out.println(i + " " + rb.select(i));
        }
    }

    public static void testRBTOrder() {
        RedBlackTree<String, Integer> rb = new RedBlackTree<>();
//        RedBlackBST<String, Integer> rb = new RedBlackBST<>();
        rb.put("S", 1);
        rb.put("E", 2);
        rb.put("A", 3);
       rb.put("R", 4);
        rb.put("C", 5);
       rb.put("H", 6);
       rb.put("X", 7);
        rb.put("M", 8);
       rb.put("P", 9);
       rb.put("L", 10);
       String str = "O";
        System.out.println(str + " " + rb.rank(str));
        for(String k: rb.keys()) {
            System.out.println(k + " " + rb.rank(k));
        }
    }

    public static void testRBTDelete() {
        RedBlackTree<String, Integer> rb = new RedBlackTree<>();
//        RedBlackBST<String, Integer> rb = new RedBlackBST<>();
        rb.put("S", 1);
        rb.put("E", 2);
        rb.put("A", 3);
        rb.put("R", 4);
        rb.put("C", 5);
        rb.put("H", 6);
        rb.put("X", 7);
        rb.put("M", 8);
        rb.put("P", 9);
        rb.put("L", 10);
//        System.out.println("红黑树大小："+ rb.size());
//        System.out.println(rb);
//        String key = "A";
//        System.out.println(key + "=对应的值=" + rb.get(key));

//        rb.deleteMin();
//        System.out.println("红黑树大小："+ rb.size());
//        System.out.println(rb);
//        rb.deleteMin();
//        System.out.println("红黑树大小："+ rb.size());
//        System.out.println(rb);
//        rb.deleteMin();
//        System.out.println("红黑树大小："+ rb.size());
//        System.out.println(rb);
//        rb.deleteMin();
//        System.out.println("红黑树大小："+ rb.size());
//        System.out.println(rb);
//        rb.deleteMax();
//        System.out.println("红黑树大小："+ rb.size());
//        System.out.println(rb);

//        rb.delete("P");
//        System.out.println("红黑树大小："+ rb.size());
//        System.out.println(rb);
//        rb.delete("S");
//        System.out.println("红黑树大小："+ rb.size());
//        System.out.println(rb);
//        rb.delete("R");
//        System.out.println("红黑树大小："+ rb.size());
//        System.out.println(rb);
//        rb.delete("L");
//        System.out.println("红黑树大小："+ rb.size());
//        System.out.println(rb);
//        rb.delete("M");
//        System.out.println("红黑树大小："+ rb.size());
//        System.out.println(rb);
    }
    public static void testBst() {
        BST<Integer, String> bst = new BST<>();
        bst.put(33, "a");
        bst.put(23, "b");
        bst.put(82, "c");
        bst.put(3, "d");
        bst.put(25, "e");
        bst.put(70, "f");
        bst.put(100, "g");
        System.out.println("初 始：" + bst);

        Integer key = 3;
//        System.out.println(key + "-" + bst.get(key));
//
//        System.out.println("最大键: " + bst.max());
//        System.out.println("最小键: " + bst.min());
//
//        key = 5;
//        System.out.println(key + " 向上取整：" + bst.ceiling(key));
//        System.out.println( key + " 向下取整：" + bst.floor(key));
//        key = 26;
//        int index = bst.rank(key);
//        System.out.println("rank(" + key + ")=" + index);
//        System.out.println("select(" + index + ")=" + bst.select(index));

//        key = 70;
//        System.out.println("删除： " + key + "=" + bst.delete(key));
//        System.out.println("删除后： " + bst);

//        System.out.println("删除最小键： " + bst.deleteMin());
//        System.out.println("删除后：" + bst);
//        System.out.println("删除最大键： " + bst.deleteMax());
//        System.out.println("删除后：" + bst);

        int lo = 0, hi = 80;
        Iterator<Integer> iterator = bst.keys(lo, hi).iterator();
        System.out.println("范围查找：" + lo + "~" + hi);
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println();
    }


    public static void testBstTraversal() {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        bst.add(33);
        bst.add(23);
        bst.add(82);
        bst.add(3);
        bst.add(25);
        bst.add(70);
        bst.add(100);

        System.out.println(bst);
    }
}
